package com.xgb.edu.tree;
/**
* 类说明
* @author xiaowu
* E-mail:865815412@qq.com
* @version 创建时间：2018年12月23日 上午10:11:09
*/
public class BinaryTree implements Tree {
	//表示根节点
	private Node root;

	public Node getRoot(){
		return root;
	}
	
	@Override
	public Node find(int key) {
		Node current = root;
		while(current != null){
			if(current.data > key){						//当前值比查找值大，搜索当前节点左子树
				current = current.leftChild;
			}else if(current.data < key){				//当前值比查找值小，搜索当前节点右子树
				current = current.rightChild;
			}else {										//搜索到预期值返回节点
				return current;
			}
		}
		return null;
	}
	
	/**
	 * 二叉树插入元素，先判断根节点是否为空，为空插入到根；否则遍历对比值，寻找插入位置
	 * @param data
	 * @return
	 */
	public boolean add(int data){
		Node newNode = new Node(data);
		if(root == null){
			root = newNode;
			return true;
		}else{
			Node current = root;
			Node parentNode = null;
			while(current != null){
				parentNode = current;
				if(current.data > data){
					current = current.leftChild;
					if(current == null){
						parentNode.leftChild = newNode;
						return true;
					}
				}else{
					current = current.rightChild;
					if(current == null){
						parentNode.rightChild = newNode;
						return true;
					}
				}
			}
		}
		return false;
	}
	

	
	@Override
	public boolean insert(int data) {
		Node newNode = new Node(data);
		if(root == null){								//当前树为空树，没有任何节点
			root = newNode;
			return true;
		}else{											//当前树不是空树，含节点
			Node current = root;
			Node parentNode = null;
			while(current != null){
				parentNode = current;
				if(current.data > data){				//当前值比插入值大，搜索左子节点
					current = current.leftChild;
					if(current == null){				//左节点为空，直接将新值插入到该节点
						parentNode.leftChild = newNode;
						return true;
					}
				}else{
					current = current.rightChild;
					if(current == null){				//右子节点为空，直接将新值插入到该节点
						parentNode.rightChild = newNode;
						return true;
					}
				}
			}
		}
		return false;
	}

	@Override
	public boolean delete(int key) {
		// TODO Auto-generated method stub
		return false;
	}

	@Override
	public void infixOrder(Node current) {
		if(current != null){
			infixOrder(current.leftChild);
			System.out.print(current.data + ",");
			infixOrder(current.rightChild);
		}

	}

	@Override
	public void prevOrder(Node current) {
		if(current != null){
			System.out.print(current.data + ",");
			prevOrder(current.leftChild);
			prevOrder(current.rightChild);
		}

	}

	@Override
	public void postOrder(Node current) {
		if(current != null){
			postOrder(current.leftChild);
			postOrder(current.rightChild);
			System.out.print(current.data + ",");
		}

	}

	@Override
	public Node findMax() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public Node findMin() {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * 二叉树查询
	 * @param key
	 * @return
	 */
	public Node findNode(int key){
		Node current = root;
		while(current != null){
			if(current.data > key){
				current = current.leftChild;
			}
			else if(current.data < key){
				current = current.rightChild;
			}else{
				return current;
			}
		}
		
		return null;
	}
	
}
